package com.spirng.leetcode.day08;

import java.util.*;
import java.util.stream.Collectors;

public class Test40 {
    public static void main(String[] args) {
        Test40 test40 = new Test40();
        test40.combinationSum2(new int[]{10,1,2,7,6,1,5},8);
    }
    ArrayList lists=new ArrayList<List<Integer>>();
    LinkedList<Integer> list=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int[] ints = Arrays.stream(candidates).sorted().toArray();
        backtracking(ints,target,0,0,new int[candidates.length]);
        return lists;
    }
    public void backtracking(int [] candidates,int target,int sum,int offSize,int [] user){
        if(sum>target){
            return;
        }
        if(sum==target){
            lists.add(new ArrayList(list));
            return;
        }
        for (int i = offSize; i < candidates.length&&sum + candidates[i] <= target; i++) {
            if(i>0&&candidates[i]==candidates[i-1]&&user[i-1]==0){
                continue;
            }
            user[i]=1;
            list.add(candidates[i]);
            backtracking(candidates,target,sum+candidates[i],i+1,user);
            list.removeLast();
            user[i]=0;
        }
    }
}
